package com.edu.leetcode.dataStruct;

/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * @作者 five-five
 * @创建时间 2021/3/30
 */
public class Demo08 {
    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        boolean b = new Demo08().searchMatrix(matrix, 13);
        System.out.println(b);
    }

    /**
     * 每行中的整数从左到右按升序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        //想法：我先拿每一行的行头来比较
        for (int i = 0; i < matrix.length; i++) {
            int[] temp = matrix[i];
            //行首
            int lineHead = temp[0];
            //行尾
            int lineFoot = temp[temp.length-1];
            if (target >= lineHead && target <= lineFoot) {
                //现在在迭代数组
                for (int num : temp) {
                    if (num == target) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
